package com.fengye.algorithms.leecode;

/**
 * @Author fengye
 * @Date 2023/4/25 9:21
 **/
public class NumberOfIslands200 {
    public int numIslands(char[][] grid) {
        int count = 0;
        int num = 0;
        for(int i=0;i< grid.length;i++) {
            for (int j = 0; j < grid[0].length;j++) {
                if(grid[i][j] == '1') {
                    count = islandCount(grid, i, j);
                    if(count > 0) {
                        num++;
                    }
                }
            }
        }
        return num;
    }

    public int islandCount(char[][] grid, int r, int c) {
        if(r<0 || r >= grid.length || c<0 || c >= grid[0].length) {
            return 0;
        }

        if(grid[r][c] != '1') {
            return 0;
        }
        // 标记已经计算过
        grid[r][c] = '2';
        int count = 1;
        int[][] visited = {{1,0}, {-1,0}, {0,1},{0,-1}};
        for(int i=0;i<visited.length;i++) {
            count += islandCount(grid, r + visited[i][0], c + visited[i][1]);
        }
        return count;
    }
}
